package lrucache;

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    static class DLinkedNode {
        public int key;
        public int value;
        public DLinkedNode prev;
        public DLinkedNode next;
        public DLinkedNode() {

        }
        public DLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    public DLinkedNode head;//双向链表的头节点
    public DLinkedNode tail;//双向链表的尾节点
    public int usedSize;//双向链表中有效数据个数
    public Map<Integer, DLinkedNode>  cache = new HashMap<>();
    public int capacity;//容量

    public LRUCache(int capacity) {
        this.head=new DLinkedNode();
        this.tail=new DLinkedNode();
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }
    //存储元素
    public void put(int key,int val){
        //1、查找这个key之前是否存储过
        DLinkedNode node = cache.get(key);
        //2、若没有存储过
        if(node==null){
            //2.1 需要实例化一个节点
            DLinkedNode dLinkedNode = new DLinkedNode(key, val);
            //2.2 存储到map当中一份
            cache.put(key,dLinkedNode);
            //2.3 把该节点存储到链表的尾巴
            addTail(dLinkedNode);
            usedSize++;
            //2.4 检查当前双向链表的有效数据个数是不是超过了capacity
            if(usedSize>capacity){
                //2.5 超过了，就需要移除头部的节点
                //记录移除的节点
                DLinkedNode remNode = removeHead();
                cache.remove(remNode.key);
                //2.6 usedSize--
                usedSize--;
            }
        }else{
            //3、若存储过
            //3.1更新这个key对应的val
            node.value=val;
            //3.2 然后将这个节点移动至尾巴处
            moveToTail(node);
        }
    }

    //将节点移动至尾巴处
    private void moveToTail(DLinkedNode node) {
        //1、先删除这个节点
        removeNode(node);
        //2、添加到尾巴节点
        addTail(node);
    }

    private void removeNode(DLinkedNode node) {
        node.prev.next=node.next;
        node.next.prev=node.prev;
    }

    //把节点存储到链表的尾巴
    private void addTail(DLinkedNode node){
        tail.prev.next=node;
        node.prev=tail.prev;
        node.next=tail;
        tail.prev=node;
    }
    //移除头部的节点
    private DLinkedNode removeHead(){
        DLinkedNode del = head.next;
        head.next=del.next;
        del.next.prev=head;
        return del;
    }
    //访问当前的key
    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 如果 key 存在，先通过哈希表定位，再移到头部
        moveToTail(node);
        return node.value;
  }


}
